1. Field of the Invention
This invention relates to cryptographic systems, and more specifically to multiparty authentication systems like public key digital signatures.
2. Description of Prior Art
The concept of a "public key" is well known in the art. To form such a key, a secret seed is first chosen, typically at random from some suitable distribution. This secret seed is then used as the input to a public key creating algorithm. The resulting public key need not be kept secret; because of the "one-way" nature of the creating algorithm, deriving the secret seed from the public key is thought to be infeasible.
An often necessary aspect of public keys is their authenticity. There may be many users of a particular public key, and each must be ensured that they have its true value. If a bogus value were to be accepted as authentic by a particular user, then that user's security might be violated by the bogus key's creator. An example solution to this problem, which is often suggested, is to publish and widely distribute a directory of public keys.
An important use of public keys is for public key digital signatures, which are called "digital signatures" here for clarity. The message to be signed by a digital signature is represented as a number. The digital signature itself is also a number. It is formed from the message by a signing algorithm which uses a private key derived from the secret seed. A digital signature can be checked as corresponding to a particular message and public key combination, by applying a checking algorithm. Because the corresponding private key is thought to be needed in forming digital signatures, they are thought to be resistant to forgery.
One inherent property of digital signatures is that they can be checked by anyone knowing the corresponding public key. Thus, if you were to give a digital signature to someone, then they could show it to anyone else. Not only would each person seeing the signature be able to check it, but they could in turn supply it to others, who could also check and distribute it. Whereas this might be an advantage in some applications, it could be undesirable in others. For example, the issuer may wish to retain some monitorability or control over the showing of signatures.
The first really practical digital signature system was disclosed by Rivest, Shamir and Adleman in "A method for obtaining digital signatures and public-Key cryptosystems, "Communications of the ACM, Vol. 21, No. 2, February 1978. This so called RSA system remains probably the best known and most widely used for digital signatures. One of its drawbacks, however, is that its public key creating algorithm requires quite a substantial amount of computation compared to that required to form its digital signatures. Like most successful public key systems devised to date, RSA is partly based on the "discrete log" problem: all of its arithmetic is done in a finite group where given the representation of an element and a large power of that element, it is thought to be infeasible to discover what the power is. In essence, RSA and its cousins require that the order of the group be known only to the signer, which imposes a significant restriction on the group, making suitable groups difficult to find and also requiring a single group per signer.
RSA does, however, allow blind signatures, as described in European Patent Publication 0139313, dated 2/5/85, claiming priority on U.S. Ser. No. 524896, titled "Blind signature systems," by the present applicant. These first disclosed blind signatures required computation during blinding to anticipate all possible signature types. This amounted to more than a single multiply per signature type anticipated. The so called "unanticipated blind signatures" require only a fixed amount of computation during blinding to anticipate an unlimited number of kinds of signatures that might potentially be applied by a signer. Such systems were described in European Patent Publication 0218305, dated 4/15/87, claiming priority on U.S. Ser. No. 784999, titled "Unanticipated blind signature systems," also by the present applicant. A remaining difficulty with the exemplary embodiments of both schemes, however, is that the signer must be fixed at the time of blinding and cannot be changed, even for so called "re-blinding".
The other widely accepted digital signature scheme was disclosed by ElGamal in "A public key cryptosystem and a signature scheme based on discrete logarithms," Advances in Cryptology: Proceedings of CRYPTO 84, G. R. Blakely and D. Chaum Eds., Springer-Verlag, 1985. Whereas it is also discrete-log based, it does not require that the order of the group be kept secret, but does require that the order be known to all signers using the same group. Its public key creation algorithm is essentially as fast as its signing algorithm, but blind signatures have not been constructed based on these ElGamal signatures.